In a typical communications system, a transmitter sends an information stream over a channel to a receiver. Typically, not all of the information stream sent by the transmitter is received by the receiver due to interference in the channel. In other situations, the information stream is distorted due to the information stream bouncing off or passing through additional mediums and received by the receiver after the primary information stream was received (phase distortion) or with less intensity (amplitude distortion).
Convolutional encoding is used to build redundancy into a data stream to detect errors and to correct errors caused by interference in the channel or distortion in the information stream. Convolutional codes have the advantage of being reliable, efficient, and able to handle high data-rate communications through low bandwidth channels.
One known method of estimating the sequence of convolutionally encoded symbols transmitted over a channel is through a Viterbi decoder. The Viterbi decoder keeps track of all the possible information streams, and outputs an information stream that is the most likely information stream sent by a sender. The Viterbi decoder uses a trellis. The trellis is a dynamic programming table whose entries are indexed by (t,s), where t is a time step and s is a state. The Viterbi decoder is limited in the time steps by a traceback length, L. At each time step, the Viterbi decoder outputs the (t-L)-th bit of the most likely information stream at time step, t, after at least L bits have been received.
Another method of decoding a convolutional code uses a sequential decoder, such as a Fano decoder or a Stack decoder, or a A* decoder. The Fano and Stack decoders search a tree, instead of the trellis, for all the possible decoder state sequences over a fixed length sequence of information symbols. The tree has the same type of states and transitions as the trellis; however, the tree has 2t nodes, where t is time. Each node represents a unique state transition path from the root. The tree is not necessarily stored explicitly, but searched implicitly via some heuristic. An error metric is used and once a leaf of the tree is found that has a good error metric, the entire path leading to that leaf is outputted. The particular error metric and search strategy chosen make one sequential decoder different from another sequential decoder. The Fano and Stack decoders use an error metric that depends not only on the received symbols and the true bits of the transition, but also on the tree level of the node being expanded. In other words, the closer the node is to a leaf of the tree, the fewer errors are likely to be introduced.
Under good Signal-to-Noise Ratio (SNR) conditions, sequential decoders are more computationally efficient than the Viterbi decoder, but, in addition to being suboptimal in terms of detection performance, they become prohibitively slow at low SNR. The A* decoder combines the reliability and performance of the Viterbi decoder while running as efficiently as a sequential decoder when the SNR is high.
The transmission of data often requires that an equalizer be incorporated in the receiver to correct for the distortions produced by the transmission medium. These distortions can include effects such as amplitude variations and multi-path propagation. Sequence estimation is used in equalizers to correct for certain types of distortions, such as inter-symbol interference. Equalizers typically employ the same methods for sequence estimation (i.e., Viterbi, Stack and Fano) as are used for the decoding of convolutional codes.
It is an important object of the invention to provide improved recovery of information from a received signal having both desired and undesired information.